树型 DP 的思路

是否为搜索二叉树（DP 法）⭐

参考左神的教程： 0:46:00

左树得是搜索二叉树
右树得是搜索二叉树
左树最大值小于 Root 节点的值
右树最小值大于 Root 节点的值

所以它向它的左树需要什么信息？

左树是否是搜索二叉树
然后左树的最大值

它向它的右树需要什么信息？

右树是否是搜索二叉树
右树的最小值

总结一下：整个判断只需用大下面三个信息：

最大值是什么？
最小值是什么？
是否是搜索二叉树？

算法如下：

    /**
     * 判断是否为二叉搜索树
     */
    public static boolean isBST(TreeNode head) {
        return process(head).isBST;
    }

    /**
     * 返回 Data 这里存了需要的三个信息
     */
    public static class ReturnData {
        boolean isBST;
        int max;
        int min;

        public ReturnData(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }

    public static ReturnData process(TreeNode x) {
        if (x == null) return null;
        // 这里其实就是拆黑盒的过程，不用管它怎么拿到的
        ReturnData leftData = process(x.left);
        ReturnData rightData = process(x.right);

        // 返回的三个信息
        int min = x.value;
        int max = x.value;
        // 这里的 min 主要取得最小值
        if (leftData != null) {
            min = Math.min(min, leftData.min);
            max = Math.max(max, leftData.max);
        }
        // 这里的 max 主要取得最大值
        if (rightData != null) {
            min = Math.min(min, rightData.min);
            max = Math.max(max, rightData.max);
        }

        boolean isBST = true;

        // 这里就是主要的判断条件
        if (leftData != null && (!leftData.isBST || leftData.max >= x.value)) isBST = false;
        if (rightData != null && (!rightData.isBST || rightData.min <= x.value)) isBST = false;

        // 把三个信息传递出去
        return new ReturnData(isBST, min, max);
    }

其实就是一种 DP（动态规划）的过程，把需要的结果传递出去

所以遇到需要从左树取信息，右树取信息的题目就可以使用这个方法来解

是否为平衡二叉树（DP 法）

平衡条件：

左子树得是平衡的
右子树也得是平衡的
左高 - 右高 <= 1

这里使用上面搜索二叉树的那个套路，分析得需要如下条件

所以判断需要两个条件：是否是平的、高度

/**
 * 判断是否为平衡二叉树
 */
public static boolean isBalancedTree(TreeNode head) {
    return process(head).isBalanced;
}

public static class ReturnType {
    public boolean isBalanced;
    public int height;

    ReturnType(boolean isBalanced, int height) {
        this.isBalanced = isBalanced;
        this.height = height;
    }
}

public static ReturnType process(TreeNode x) {
    if (x == null) return new ReturnType(true, 0);
    // 同样拆黑盒，不用管，总之它代表左边或右边的结果
    ReturnType leftData = process(x.left);
    ReturnType rightData = process(x.right);

    int heightMax = Math.max(leftData.height, rightData.height) + 1;

    boolean isBalanced = leftData.isBalanced && rightData.isBalanced
            && Math.abs(leftData.height - rightData.height) < 2;

    return new ReturnType(isBalanced, heightMax);
}

是否为满二叉树（DP 法）

按照上面搜索二叉树的方法，总结：判断满二叉树只需两个个条件

高度
节点数量

依旧是之前的套路

    /**
     * 判断是否为满二叉树
     */
    public static boolean isFBT(TreeNode head) {
        ReturnData data = process(head);
        System.out.println(data.height + "   " + data.nodeCount);
        return data.nodeCount == (Math.pow(2, data.height) - 1);
    }

    public static class ReturnData {
        int height;
        int nodeCount;

        public ReturnData(int height, int nodeCount) {
            this.height = height;
            this.nodeCount = nodeCount;
        }
    }

    public static ReturnData process(TreeNode x) {
        if (x == null) return new ReturnData(0, 0);
        // 这里其实就是拆黑盒的过程，不用管它怎么拿到的
        ReturnData leftData = process(x.left);
        ReturnData rightData = process(x.right);

        int height = Math.max(leftData.height, rightData.height) + 1;
        int nodeCount = leftData.nodeCount + rightData.nodeCount + 1;

        return new ReturnData(height, nodeCount);
    }

补充：其实这里的 Math.pow(2, data.height) 可以使用位操作来代替（因为底数是 2）

// 最后一行改成如下：
data.nodeCount == ((1 << data.height) - 1);

不适合的情况

二叉树中的中位数

这个也是左神的补充题目，上面的套路就使用不了，因为判断中位数需要取得 整体 Tree 中的数 来判断的

二叉树的最近公共祖先

保存整体 Tree 中的数，依次取得 TreeNode 的父亲

    /**
     * 二叉树的最近公共祖先
     */
    public static int lca(TreeNode head, TreeNode o1, TreeNode o2) {
        HashMap<TreeNode, TreeNode> fatherMap = new HashMap<>();
        fatherMap.put(head, head);
        process(head, fatherMap);
        // 用来存储 o1 的 father 链
        HashSet<TreeNode> set1 = new HashSet<>();
        TreeNode cur = o1;
        while (cur != fatherMap.get(cur)) {
            set1.add(cur);
            cur = fatherMap.get(cur);
        }
        // 别忘了它们之间一定有的共同 father 是 root
        set1.add(head);

        cur = o2;
        // 再遍历 o2 取得共同 father 为止（判断 o1 的父亲链是否包含 o2 的某个父亲，如果存在则说明这个就是它们的公共父亲）
        while (!set1.contains(cur)) {
            cur = fatherMap.get(cur);
        }
        return cur.value;
    }

    public static void process(TreeNode head, HashMap<TreeNode, TreeNode> fatherMap) {
        if (head == null) return;
        if (head.left != null) fatherMap.put(head.left, head);
        if (head.right != null) fatherMap.put(head.right, head);
        process(head.left, fatherMap);
        process(head.right, fatherMap);
    }

这种写法的时间、空间复杂度为 $O(n)$

补充一个 Golang 版本的代码：

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func lowestCommonAncestor(root *TreeNode, o1 int, o2 int) int {
    fatherMap := make(map[int]int)
    fatherMap[root.Val] = root.Val
    dfs(root, fatherMap)

    o1M := make(map[int]struct{}) // 用来存 o1 的父节点链
    cur := o1
    // 找到 cur 的父亲们
    for fatherMap[cur] != cur { // 结束条件其实就是 fatherMap[root.Val] == root.Val
        o1M[cur] = struct{}{}
        cur = fatherMap[cur]
    }
    // 别忘了加 root
    o1M[root.Val] = struct{}{}
    cur = o2

    // 遍历 o2 的父节点链，判断 o2 的父亲链哪个跟 o1 的重合了
    for true {
        if _, ok :=  o1M[cur]; !ok {
            cur = fatherMap[cur]
        } else {
            return cur
        }
    }

    return cur
}

// 把所有节点的直接父节点存进去
func dfs(head *TreeNode, m map[int]int) {
    if head == nil {
        return
    }
    if head.Left != nil {
        m[head.Left.Val] = head.Val
    }

    if head.Right != nil {
        m[head.Right.Val] = head.Val
    }

    dfs(head.Left, m)
    dfs(head.Right, m)
}

是否为搜索二叉树（DP 法）⭐​

是否为平衡二叉树（DP 法）​

是否为满二叉树（DP 法）​

不适合的情况​

二叉树中的中位数​

二叉树的最近公共祖先​